/*************************************************************************
	> File Name: quicksort.cpp
	> Author: likang
	> Mail: likang@ict.ac.cn
	> Created Time: 四  8/10 23:18:53 2017
 ************************************************************************/

#include<iostream>
using namespace std;

int partition(int* arr, int low, int high) {

    int pivot = arr[high];
    int s = low - 1;
    for (int i = low; i < high; ++i) {
        if (arr[i] < pivot) {
            ++s;
            if (s != i) {
                int tmp = arr[s];
                arr[s] = arr[i];
                arr[i] = tmp;
            }
        }
    }

    ++s;
    int tmp = arr[s];
    arr[s] = arr[high];
    arr[high] = tmp;
    return s;
}

void quickSort(int* arr, int low, int high) {
    
    if (low >= high) {
        return;
    }

    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
}

int main(void) {

    int a[] = {1};
    quickSort(a, 0, 0);
    cout << a[0] << endl;

    int b[] = {2,1};
    quickSort(b, 0, 1);
    for (int i = 0; i < 2; ++i) {
        cout << b[i] << " ";
    }
    cout << endl;

    int c[] = {1,3,4,2,6,8,1};
    quickSort(c, 0, 6);

    for (int i = 0; i < 7; ++i) {
        cout << c[i] << " ";
    }
    cout << endl;
}
